Reverse Engineering of Irreducible Polynomials in GF(2^m) Arithmetic

摘要

Current techniques for formally verifying circuits implemented in Galoisfield (GF) arithmetic are limited to those with a known irreducible polynomialP(x). This paper presents a computer algebra based technique that extracts theirreducible polynomial P(x) used in the implementation of a multiplier inGF(2^m). The method is based on first extracting a unique polynomial in Galoisfield of each output bit independently. P(x) is then obtained by analyzing thealgebraic expression in GF(2^m) of each output bit. We demonstrate that thismethod is able to reverse engineer the irreducible polynomial of an n-bit GFmultiplier in n threads. Experiments were performed on Mastrovito andMontgomery multipliers with different P (x), including NIST-recommendedpolynomials and optimal polynomials for different microprocessor architectures.